1) Field of the Invention
The present invention relates to database management in general and in particular to databases used to route packets in communications networks.
2) Prior Art
In a data communications network a forwarding device such as a router or the like is used to direct data packets from a source device to a destination device. In order to effectuate the forwarding of packets a database hereinafter termed “Forwarding Table” is generated and maintained in the router. FIG. 1 shows a graphical representation of the prior art forwarding table implemented in a router such as Router 40 FIG. 2) consisting of Destination, Subnet Subfield, Next Hop IP address subfield and Outgoing Interface subfield.
The forwarding entries in FIG. 1 are derived from the network configuration shown in FIG. 2 which will be described in greater details hereinafter. Suffice it to say at this point the destination addresses of devices attached to the router are recorded in the Destination Subnet subfield; the next hop IP address to which a packet is to be routed in order to be delivered to a particular destination address is recorded in the Next Hop IP Address subfield and the exit port or interface through which the packet exit is recorded in the outgoing interface subfield of FIG. 1. The coding in FIG. 1 is decimal with ‘XXX’ indicating Don't Care state.
With the above nomenclature each entry in FIG. 1 includes the destination subnet, the next Hop IP address and the outgoing port or interface. With respect to the first entry in the Prior Art Routing Table of FIG. 1 only the first byte “11” of the destination subnet entry is of value or interest. The other bytes ‘XXX’ are Don't Care and of no interest. The entry in the Next Hop IP address indicate that only one device with the IP address “11.0.0.1” is coupled to subnet 11.X.X.X and the outgoing interface is I2. Similarly, the second entry in the table indicates only one device with Next IP Address 9.0.0.1 is coupled to Destination Subnet 10.X.X.X and the outgoing interface is I1.
The other listings in the prior art forwarding table of FIG. 1 shows the destination subnet and corresponding Next Hop IP Address are identical and identify each end stations connected to Destination subnet 9.X.X.X. It is also obvious that the size of the table could be extremely large as the number of end stations increases. The showing in the routing table of FIG. 1 indicates 100 end stations labeled 9.0.0.2 through 9.0.0.100 connected to Subnet 9.X.X.X which is directly attached to Interface or Port I1 of Router 40. But in reality and as more users are connected to the internet and other types of networks it would not be unreasonable to have single or multiple directly connected subnets attaching tens of thousands of end stations to a router. Because each end station has to be recorded the size of the forwarding table would be unacceptable.
The prior art requirement to record all directly connected end stations in the forwarding table creates several problems. One of the problems is that a large amount of storage is required to record large number of end stations. The storage has to be relatively fast in order to meet performance requirements of most systems. The type of storage required for use in this application tends to be expensive and as a result increases the overall price of the forwarding device.
Another problem associated with a large forwarding table is that it tends to impair the throughput or performance of the forwarding device. As is well known the forwarding table contains information that is used to route packets. To accomplish this task the forwarding device includes routing functions that routinely scan the table to detect entries with destination addresses matching destination addresses in the packet being routed. This searching has to be done in a finite time interval which is sensitive, among other things, to the table size and memory speed. In fact, as the size of the forwarding table increases the time interval required to complete a search increases until the finite time is surpassed. Arguably, high performance specialized processors could be used as the search engine. But use of this type of processors is costly and would increase the overall cost of the forwarding device.
Another factor contributing to performance degradation is maintenance of the forwarding table to reflect the insertion and de-insertion of nodes into/from the network. This requires deleting from the forwarding table entries for de-inserted nodes and adding entries for newly inserted nodes. More time and resources are required to maintain a large forwarding table than would be required to maintain an optimum size forwarding table.
In view of the above there is a need to provide optimized forwarding tables for use to forward packets within communications networks.